package com.mc.string;

public class KMP {
	
	private static int[] computeNext(char[] pattern){
		int[] next = new int[pattern.length];
		int k = 0;
		next[0] = 0;
		for(int i=1;i<next.length;i++){
			//当前匹配失败时进行递归，不断递归判断是否存在子对称，k=0说明不存在子对称
			while(pattern[k]!=pattern[i]&&k>0)
				k = next[k-1];		
			//找到了子对称，或者直接继承了前面的对称性
			if(pattern[k]==pattern[i])
				k++;
			next[i] = k;
		}
		return next;
	}
	
	public static boolean match(String target,String pattern){
		int[] next = computeNext(pattern.toCharArray());
		int k = 0;
		for(int i=0;i<target.length();i++){
			while(target.charAt(i)!=pattern.charAt(k)&&k>0)
				k = next[k-1];
			
			if(target.charAt(i)==pattern.charAt(k))
				k++;
				
			if(k==pattern.length())
				return true;
		}
		return false;
	}
	
	public static void main(String[] args){
		boolean result = KMP.match("djshakliouwdkdhjsakagctagctagcagctagct", "agctagcagctagct");
		System.out.println(result);
	}
}
